# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def maxPathSum(self, root: TreeNode) -> int:
        res = float('-inf')

        def dfs(root):
            nonlocal res
            if not root:
                return float('-inf')

            left_max = dfs(root.left)
            right_max = dfs(root.right)

            res = max(res, left_max + root.val, right_max + root.val, right_max + left_max + root.val, root.val)

            return max(root.val, root.val + left_max, root.val + right_max)

        dfs(root)

        return res


class Solution:
    def __init__(self):
        self.maxSum = float("-inf")

    def maxPathSum(self, root: TreeNode) -> int:
        def maxGain(node):
            if not node:
                return 0

            # 递归计算左右子节点的最大贡献值
            # 只有在最大贡献值大于 0 时，才会选取对应子节点
            leftGain = max(maxGain(node.left), 0)
            rightGain = max(maxGain(node.right), 0)

            # 节点的最大路径和取决于该节点的值与该节点的左右子节点的最大贡献值
            priceNewpath = node.val + leftGain + rightGain

            # 更新答案
            self.maxSum = max(self.maxSum, priceNewpath)

            # 返回节点的最大贡献值
            return node.val + max(leftGain, rightGain)

        maxGain(root)
        return self.maxSum


'''
你看我这里写的：它分为三种情况，取其中最大的：
停在当前子树的 root，收益：root.val。 走入左子树，最大收益：root.val + dfs(root.left)。 
走入右子树，最大收益：root.val + dfs(root.right)。
取其中最大的就是这样，求走入一个子树的最大的收益，你不能把左右子树都加上，
比如走入左子树获，不能折回来掉头，走入右子树，路径就重叠了，不符合定义，所以你不能把两个都加上。
'''
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def maxPathSum(self, root: TreeNode) -> int:
        res = float('-inf')
        def dfs(root):
            nonlocal res
            if not root: return float('-inf')
            left_max = max(dfs(root.left),0)
            right_max = max(dfs(root.right),0)
            res = max(res, left_max + right_max + root.val)
            return root.val+max(left_max,right_max)
        dfs(root)
        return res
class Solution:
    def maxPathSum(self, root: TreeNode) -> int:
        res = float('-inf')
        def dfs(root):
            nonlocal res
            if not root: return float('-inf')
            right_max = max(dfs(root.right),0)
            left_max = max(dfs(root.left),0)
            res = max(res, root.val + left_max +right_max)
            return root.val + max(left_max,right_max)
        dfs(root)
        return res